package cn.rocky.structures.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 广度优先遍历
 */
public class GraphBFS {

    private boolean[] visited;

    private ArrayList<Integer> order = new ArrayList<>();

    private Graph G;

    public GraphBFS(Graph G) {
        this.G = G;
        visited = new boolean[G.getV()];
        for (int v = 0; v < G.getV(); v++) {
            if (!visited[v]) {
                bfs(v);
            }
        }
    }

    private void bfs(int s) {
        Queue<Integer> queue = new LinkedList<>();
        visited[s] = true;
        queue.add(s);
        while (!queue.isEmpty()) {
            int v = queue.remove();
            order.add(v);
            for (int w : G.adj(v)) {
               if (!visited[w]) {
                   queue.add(w);
                   visited[w] = true;
               }
            }
        }
    }

    public Iterable<Integer> order() {
        return order;
    }

    public static void main(String[] args) {
        Graph graph = new Graph(7, 6);
        graph.insert(0, 1);
        graph.insert(0, 3);
        graph.insert(1, 2);
        graph.insert(1, 5);
        graph.insert(2, 4);
        graph.insert(2, 6);
        GraphBFS dfs = new GraphBFS(graph);
        System.out.println(graph);
        System.out.println(dfs.order());
    }
}
